This relates to a method and apparatus for comparing strings by comparing hash codes associated with such strings. It is especially useful in comparing strings in the environment of parallel logic programming.
One example of a logic programming language is PROLOG (PROgramming in LOGic). W. F. Clocksin and C. S. Mellish, Progamming in Prolog, (Springer-Verlag, 2d Ed. 1984) (hereinafter "Clocksin"). As indicated in Clocksin there are many different implementations of Prolog currently available. Clocksin describes at length a "core Prolog" and provides in Appendices D and E descriptions of the implementation of Prolog for the DEC system-10 and for Z80-based microcomputers running under the CP/M operating system. DEC system-10 Prolog User's Manual, Dept. of Artificial Intelligence, University of Edinburgh (Edinburgh, Scotland); micro-PROLOG: Programming in Logic, by K. L. Clark and F. G. McCabe (Prentice-Hall, 1984). Clocksin also references at page 288 a PROLOG system that runs under UNIX as described in C-Prolog User's Manual, CAAD Studio, Dept. of Architecture, Univ. of Edinburgh, (Edinburgh, Scotland) and a system which runs on several computers from a Z-80 under CP/M to a VAX under VMS as described in Prolog-1 User's Manual, Expert Systems Ltd. (9 West Way, Oxford, England). (DEC system-10, VAX, VMS, Z80 and CP/M are all trademarks).
It is common in any implementation of PROLOG to generate many strings of data. In conventional implementations of PROLOG, all these strings are stored in one large string area or table and the strings are referenced by pointers to the addresses of the strings in the table. In such an arrangement each different string need be stored only once in the table; and the same pointer can be used at many different points in a program to refer to the same string.
A basic operation in logic programming is unification, a process which requires the comparison of strings. See Clocksin .sctn.10-4, which is incorporated herein by reference. Since each string in the table has a unique pointer, such comparison can be effected by comparing the pointers to the strings. If the pointers are different, they point to different strings. If they are the same, the strings likewise are the same.
Such a comparison technique, however, works only in a centralized organization where pointers can be systematically assigned to the individual strings so that there is a one-to-one relationship between the different pointers and the different strings. In operating systems where assignments of pointers to strings are being made simultaneously by two or more programs running in parallel, such assignments cannot readily be made because the parallel programs must run independently to achieve reasonable levels of efficiency. As a result, in systems such as Concurrent PROLOG (Ehud Shapiro, "A Subset of Concurrent Prolog and Its Interpreter", Technical Report TR-003 (ICOT, Tokyo, 1983)), there is no one-to-one relationship between different pointers and different strings and strings cannot be compared by just comparing their pointers.